package pers.whj.util.tree;

public class BinarySearchTreeImpl<T extends Comparable<T>> extends BinaryTreeImpl<T> implements BinarySearchTree<T> {
    public BinarySearchTreeImpl() {
    }

    @Override
    public boolean insert(T data) {
        checkInsertData(data);
        Node<T> node = this.root;
        Node<T> parent = null;
        while (node != null) {
            parent = node;
            if (node.data.compareTo(data) == 0) {
                return false;
            } else if (node.data.compareTo(data) < 0) {
                node = node.right;
            } else {
                node = node.left;
            }
        }
        if (parent == null) {
            this.root = new Node<>(data);
            this.size = 1;
        } else {
            if (data.compareTo(parent.data) < 0) {
                parent.left = new Node<>(data);
            } else {
                parent.right = new Node<>(data);
            }
            this.size++;
        }
        return true;
    }

    @Override
    public boolean insert(TreePath treePath, T data) {
        return insert(data);
    }

    @Override
    public boolean insert(String treePath, T data) {
        return insert(data);
    }

    @Override
    public boolean insertLeft(T parent, T data) {
        return insert(data);
    }

    @Override
    public boolean insertRight(T parent, T data) {
        return insert(data);
    }

    @Override
    public boolean remove(T data) {
        if (data != null) {
            remove(data, this.root, null);
        }
        return false;
    }

    @Override
    public T min() {
        Node<T> node = min(this.root);
        return node == null ? null : node.data;
    }

    @Override
    public T max() {
        Node<T> node = max(this.root);
        return node == null ? null : node.data;
    }

    @Override
    @SuppressWarnings({"unchecked"})
    public T precursor(T data) {
        final Object[] arr = {null, null};
        if (data != null) {
            final T target = data;
            inOrder(this.root, (data1, index) -> {
                arr[1] = data1;
                if (data1.equals(target)) {
                    return false;
                } else {
                    arr[0] = data1;
                    return true;
                }
            }, new int[]{0});
        }
        if (arr[0] != null && arr[1].equals(data)) {
            return (T) arr[0];
        }
        return null;
    }

    @Override
    @SuppressWarnings({"unchecked"})
    public T successor(T data) {
        final Boolean[] flag = {false};
        final Object[] arr = {null};
        if (data != null) {
            final T target = data;
            inOrder(this.root, (data1, index) -> {
                if (flag[0]) {
                    arr[0] = data1;
                    return false;
                }
                if (data1.equals(target)) {
                    flag[0] = true;
                }
                return true;
            }, new int[]{0});
        }
        if (flag[0] && arr[0] != null) {
            return (T) arr[0];
        }
        return null;
    }

    @Override
    public boolean buildCompleteBinaryTree(T[] data) {
        if (data == null) {
            return false;
        }
        clear();
        for (T tmp : data) {
            insert(tmp);
        }
        return true;
    }

    @Override
    public boolean buildByPreOrderAndInOrder(T[] preOrder, T[] inOrder) {
        return buildCompleteBinaryTree(preOrder);
    }

    @Override
    public boolean buildByPostOrderAndInOrder(T[] postOrder, T[] inOrder) {
        return buildCompleteBinaryTree(postOrder);
    }

    @Override
    public boolean buildByLevelOrderAndInOrder(T[] levelOrder, T[] inOrder) {
        return buildCompleteBinaryTree(levelOrder);
    }

    @Override
    protected Node<T> parentOf(Node<T> parent, Node<T> node) {
        if (parent == null || node == this.root) {
            return null;
        }
        if (parent.left != null) {
            if (parent.left.data.equals(node.data)) {
                return parent;
            } else if (node.data.compareTo(parent.data) < 0) {
                return parentOf(parent.left, node);
            }
        }
        if (parent.right != null) {
            if (parent.right.data.equals(node.data)) {
                return parent;
            } else if (node.data.compareTo(parent.data) > 0) {
                return parentOf(parent.right, node);
            }
        }
        return null;
    }

    @Override
    protected Node<T> search(Node<T> node, T data) {
        if (data == null || node == null) {
            return null;
        }
        while (node != null && node.data.compareTo(data) != 0) {
            if (node.data.compareTo(data) < 0) {
                node = node.right;
            } else {
                node = node.left;
            }
        }
        return node;
    }

    @Override
    protected boolean getTreePath(Node<T> node, TreePath treePath, T data) {
        // assert data is not null
        if (node == null) {
            return false;
        }
        if (data.equals(node.data)) {
            return true;
        }
        if (data.compareTo(node.data) < 0) {
            treePath.append(BinaryTreePath.LEFT);
            return getTreePath(node.left, treePath, data);
        } else {
            treePath.append(BinaryTreePath.RIGHT);
            return getTreePath(node.right, treePath, data);
        }
    }

    @Override
    protected boolean remove(Node<T> node) {
        return remove(node.data, this.root, null);
    }

    @Override
    protected boolean remove(Node<T> node, Node<T> parent) {
        if (node != null) {
            return remove(node.data, this.root, null);
        }
        return false;
    }

    protected boolean remove(T data, Node<T> node, Node<T> parent) {
        while (node != null && data.compareTo(node.data) != 0) {
            parent = node;
            if (data.compareTo(node.data) < 0) {
                node = node.left;
            } else {
                node = node.right;
            }
        }
        if (node == null) {
            return false;
        }
        if (node.left != null && node.right != null) {
            Node<T> tmp = node.right;
            while (tmp.left != null) {
                tmp = tmp.left;
            }
            node.data = tmp.data;
            return remove(tmp.data, node.right, node);
        }
        Node<T> tmp = node.left == null ? node.right : node.left;
        if (parent == null) {
            this.root = tmp;
        } else {
            if (node == parent.left) {
                parent.left = tmp;
            } else {
                parent.right = tmp;
            }
        }
        node.reset();
        this.size--;
        return true;
    }

    protected Node<T> min(Node<T> node) {
        if (node == null) {
            return null;
        }
        while (node.left != null) {
            node = node.left;
        }
        return node;
    }

    protected Node<T> max(Node<T> node) {
        if (node == null) {
            return null;
        }
        while (node.right != null) {
            node = node.right;
        }
        return node;
    }
}